package sort;

/**
 * @author zxl
 * @version 1.0
 * @date 2021/12/5 14:51
 * 快速排序   将数组的第一个元素作为轴点，然后从右向左扫描，当扫描的值大于轴点值，则end--（end最后元素的位置），不做操作，
 *          当扫描的值小于等于轴点值，将end的值覆盖给begin，然后交换扫描的方向
 */
public class QuickSorting {
    static int[] a = new int[]{25,3,5,2,11,56,32,43,12,54,76,90,31,67,45,76,53,87,21};
    public static void main(String[] args) {
        sort(0,a.length);
        for (int i : a) {
            System.out.print(i + " ");
        }
    }

    private static void sort(int begin, int end) {
        // 当一次轴点完成后，将剩下左右的再分，直到分到只剩一个元素为轴点
        if(end - begin < 2){
            return;
        }

        // 确定轴点的位置
        int mid = sortIndex(begin,end);
        // 递归调用
        sort(begin,mid);
        sort(mid+1,end);

    }

    private static int sortIndex(int begin, int end) {
        //轴点位置  取出轴点备份
        int pivot = a[begin];
        //将end的值指向最后一个元素
        end--;

        // 三层while循环
        while(begin < end){
            //反向扫描  开始为反向扫描
            while (begin < end){
                //当扫描的位置大于轴点的位置   这里不用等于，可保证每次分割左右两边都是均匀的，保证了效率，但是不稳定
                //                         如果使用等于，即每次分割不均匀，但是保证了稳定性
                if(pivot < a[end]){
                    // 不做操作 end--
                    end--;
                }else {
                    a[begin++] = a[end];
                    // 变为正向扫描
                    break;
                }
            }
            //正向扫描
            while (begin < end){
                //当扫描的位置大于轴点的位置
                if(pivot > a[begin]){
                        // 不做操作 begin++
                        begin++;
                }else {
                    a[end--] = a[begin];
                    break;
                }
            }
        }
        // 将轴点的值放回到最后空元素的位置
        a[begin] = pivot;
        //返回最后轴点的位置
        return begin;
    }

}
